//package edu.oregonstate.eecs.cs331.assn1;

import java.awt.*;
import java.awt.event.*;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.FileReader;
import java.io.IOException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Hashtable;
import javax.swing.JButton;
import javax.swing.JPanel;
import java.util.Stack;
import java.util.LinkedList;

/**
 * This class stores the maze and provides functions construct a maze given a
 * file (through Mazepanel(String filename)) as well as solving the maze.
 * 
 * The maze is physically stored in MazeCell[][] cells, and the MazePanel is
 * also aware of the indices into cells at which the start and finish can be
 * found (as well as the dimensions of the 2-D array.
 */
public class MazePanel extends JPanel {

	// These are the types of searches you can do
	public final static String BREADTH_FIRST_SEARCH = "bfs";
	public final static String DEPTH_FIRST_SEARCH = "dfs";
	public final static String ITERATIVE_DEEPENING_DEPTH_FIRST_SEARCH = "iddfs";
	public final static String A_STAR_SEARCH = "astar";

	// Constants for GUI layout
	public static final int buttonSizeX = 100;
	public static final int buttonSizeY = 40;

	private JButton startButton;

	// This member is in charge of storing the graphical representation
	// of the maze as a whole, as well as the individual MazeCells which
	// are to be drawn
	private JPanel grid;

	// This 2-D array of MazeCell is instantiated in the setUp() function,
	// and initialized in the MazePanel(String filename) function.
	// The indexing works as cells[x][y] where
	// 0 <= x < width
	// 0 <= y < height
	private MazeCell[][] cells;

	public static int maxX; // The maximum x coordinate value

	public static int maxY; // The maximum y coordinate value

	// Boolean reprsenting whether or not a new thread should be kicked off
	// (don't worry about this data for your assignment)
	private boolean running = true;

	private int startXIdx; // pair of indices which represents where the

	private int startYIdx; // start location can be found

	private int finishXIdx; // same with the finish location

	private int finishYIdx;

	private ArrayList<MazeCell> fringe = new ArrayList();
	
	private ArrayList<MazeCell> closedList = new ArrayList();
	
	//private Hashtable closedList = new Hashtable();
	
	// The starting cell
	private MazeCell startCell;

	// The finish cell
	private MazeCell finishCell;

	// Specifies the search mode ie. bfs, dfs, iddfs, or astar.
	private String searchMode;

	// Leave the line below in your code. You won't need to know what it is for
	// this course.
	private static final long serialVersionUID = 1L;
	private boolean offer;

	/**
	 * Parses the actual maze layout part of the file
	 * @param reader The BufferedReader object reading the file
	 * @throws IOException 
	 * @throws MazeFileFormatException
	 */
	private void parseMazeFileBody(BufferedReader reader) throws IOException,
			MazeFileFormatException {
		String line = reader.readLine(); // skip a blank line
		line = reader.readLine();
		int y = 0;
		while (line != null) {
			if (y > maxY) {
				throw new MazeFileFormatException("Too many rows in maze file");
			}
			String tokens[] = line.split("\\s+");
			if (tokens.length > maxX) {
				throw new MazeFileFormatException(
						"Too many columns in maze line: " + line);
			}
			for (int x = 0; x < tokens.length; x++) {
				// setup the cell with type and location information
				int type = Integer.parseInt(tokens[x]);
				cells[x][y].setType(type);

				// is the cell a special one?
				if (x == startXIdx && y == startYIdx)
					cells[x][y].setStart();
				else if (x == finishXIdx && y == finishYIdx)
					cells[x][y].setFinish();

			}
			line = reader.readLine();
			y++;
		}
		reader.close();
	}

	/**
	 * This constructor takes a filename where a maze description can be found,
	 * then creates the maze objects that the file corresponds to.
	 * 
	 * @param filename
	 *            The filename of the maze description
	 * @param mode
	 *            The search mode to use
	 * @throws FileNotFoundException
	 * @throws IOException
	 * @throws MazeFileFormatException
	 */
	public MazePanel(String filename, String mode)
			throws FileNotFoundException, IOException, MazeFileFormatException {
		this.searchMode = mode;
		BufferedReader reader = new BufferedReader(new FileReader(filename));
		StringTokenizer tokenizer;
		String line;

		// first line is dimensions
		try {
			line = reader.readLine();
			tokenizer = new StringTokenizer(line);

			maxX = Integer.parseInt(tokenizer.nextToken());
			maxY = Integer.parseInt(tokenizer.nextToken());
		} catch (Exception e) {
			System.out
					.println("Problem on first line of input(maze dimensions)");
			e.printStackTrace();
		}

		// now we know our size, we can setUp;
		setUp();

		// second line is start_x start_y finish_x, finish_y
		try {
			line = reader.readLine();
			tokenizer = new StringTokenizer(line);

			startXIdx = Integer.parseInt(tokenizer.nextToken());
			startYIdx = Integer.parseInt(tokenizer.nextToken());

			finishXIdx = Integer.parseInt(tokenizer.nextToken());
			finishYIdx = Integer.parseInt(tokenizer.nextToken());

			startCell = cells[startXIdx][startYIdx];
			finishCell = cells[finishXIdx][finishYIdx];
		} catch (Exception e) {
			System.out
					.println("Problem on second line of input(start, finish locations)");
			e.printStackTrace();
		}

		parseMazeFileBody(reader);

		// file parsed, now compute some metadata
		addNeighbors();
	}

	/**
	 * This function creates all the swing components that draw the grid of
	 * cells. It also instantiates the cells themselves.
	 * 
	 * Precondition: constructor has set up dimensions of the grid
	 */
	private void setUp() {
		startButton = new JButton("Start");
		grid = new JPanel();
		cells = new MazeCell[maxX][maxY];
		running = true; // controls loop in run method

		setBackground(new Color(255, 255, 200));
		setLayout(null);
		setSize(maxX * MazeCell.CELL_W, 50 + maxY * MazeCell.CELL_H);
		setLocation(0, 0);

		// start button
		startButton.setSize(buttonSizeX, buttonSizeY);
		startButton.setLocation(10, 10);
		startButton.setVisible(true);
		startButton.setFont(new Font("Ariel", Font.BOLD, 24));
		startButton.addActionListener(new StartListener());

		// grid
		grid.setSize(maxX * MazeCell.CELL_W, maxY * MazeCell.CELL_H);
		grid.setLocation(10, 70);
		grid.setVisible(true);

		// Note: GridLayout takes rows, cols
		grid.setLayout(new GridLayout(maxY, maxX));
		for (int j = 0; j < maxY; j++) {
			for (int i = 0; i < maxX; i++) {
				cells[i][j] = new MazeCell(i, j);
				grid.add(cells[i][j]);
			}
		}
		add(startButton);
		add(grid);
	}

	/**
	 * This function is responsible for making each cell aware of its neighbors.
	 * We do this by examining type information on each of the cells, as well as
	 * bounds checking on the address of the neighbor. Note: You need to check
	 * "two walls". For instance, if you want to go east, you need to make sure
	 * that the current square doesn't have a wall to the east and that the
	 * square to the east doesn't have a wall to the west.
	 */
	private void addNeighbors() {
		for (int i = 0; i < maxX; i++)
			for (int j = 0; j < maxY; j++) {
				// Can go south
				if (((cells[i][j].getType() & 1) == 0)
						&& addressInBounds(i, j + 1)
						&& ((cells[i][j + 1].getType() & 4) == 0))
					cells[i][j].setSouthNeighbor(cells[i][j + 1]);
				// Can go east
				if (((cells[i][j].getType() & 2) == 0)
						&& addressInBounds(i + 1, j)
						&& ((cells[i + 1][j].getType() & 8) == 0))
					cells[i][j].setEastNeighbor(cells[i + 1][j]);
				// Can go north
				if (((cells[i][j].getType() & 4) == 0)
						&& addressInBounds(i, j - 1)
						&& ((cells[i][j - 1].getType() & 1) == 0))
					cells[i][j].setNorthNeighbor(cells[i][j - 1]);
				// Can go west
				if (((cells[i][j].getType() & 8) == 0)
						&& addressInBounds(i - 1, j)
						&& ((cells[i - 1][j].getType() & 2) == 0))
					cells[i][j].setWestNeighbor(cells[i - 1][j]);
			}
	}

	/**
	 * Helper function to addNeighbors(), it takes 2 indices and returns whether
	 * or not that pair of indices maps into the cell grid.
	 * 
	 * @param x
	 *            x-Index of a potential cell in the grid
	 * @param y
	 *            y-Index of a potential cell in the grid
	 * @return true if the address will not cause a runtime error
	 */
	private boolean addressInBounds(int x, int y) {
		return (x >= 0 && y >= 0 && x < maxX && y < maxY);
	}

	public void paintComponent(Graphics g) {
		super.paintComponent(g);
	}

/*lukes
	public boolean breadthFirstSearch(MazeCell start){
		fringe.add(start);
		boolean done = false;
		while(!done){
			done = GraphSearch();
		}
		return done;//
	}
*/
	
/* Forrest  - http://en.wikipedia.org/wiki/Breadth-first_search */

	public boolean breadthFirstSearch(MazeCell start){
		boolean done = false;
		LinkedList<MazeCell> nextQueue = new LinkedList<MazeCell>();
		LinkedList<MazeCell> traversed = new LinkedList<MazeCell>();
		
		nextQueue.offer(start);
		
		while(!done)
		{
		MazeCell node = null;
		if ( (node = nextQueue.remove()) == null) ;
            {
            break;  //exit early if we're out of next elements to search...
            }
            traversed.addFirst(node);
        if (node.isFinish())
        	{
        	done=true;
        	break;
        	}
        else {
			//Enqueue new neighbors
			for (MazeCell neighbor : MazeCell.neighbors) {
				if (!traversed.contains(neighbor) 
				&& !nextQueue.contains(neighbor)) {
					nextQueue.offer(neighbor);
				}
			}

        }
	}
		
		return done;
	}
	public boolean depthFirstSearch(MazeCell start){
		fringe.add(start);
		Stack<MazeCell> nextStack = new Stack<MazeCell>();
		Stack<MazeCell> traversed = new Stack<MazeCell>();
		
		boolean done = false;
		nextStack.add(start);
		while(!done)
		{
			MazeCell node = nextStack.pop();
			traversed.push(node);
			
			if(node.isFinish())
			{
				done=true;
				break;
			}
			else {
			//nextStack.push(expand(node));
			}
		}

		return done;
	}
	
	/*
	 * for iddfs -- must do a depth-limited search first. 
	 * 
	 * pseudocode: 
	 * 		function depth-limited-search(problem,limit) returns solution or fail
	 * 			return recursive-dls(make-node(problem.start),problem,limit)
	 * 
	 * 		function recursive-dls(node,problem,limit) return solution,failure
	 * 			if problem.goal-test(node,STATE) then return SOLUTION(node)
	 * 			else if limit = 0 then return cutoff
	 * 			else
	 * 				cutoff_occured=false
	 * 				foreach action in problem.actions(node,STATE) do
	 * 					child = child-node(problem,node,action)
	 * 					result = recursive-dls(child,problem,limit-1)
	 * 					if result == cutoff then cutoff_occured = true
	 * 					else if result !=failure then return result
	 * 				if (cutoff_occured) then return cutoff else return failure
	 * 
	 * FUNCTION: Iterative-depening-search(problem) returns solution or fail
	 * 	for depth=0 to infinity do
	 * 		result=depth-limited-search(problem,depth)
	 * 		if result !=cutoff then return result 
	 * 
	 * 
	 */
	public boolean iDDFS(MazeCell start){
		fringe.add(start);
		boolean done = false;
		return done;
	}
	
	public boolean	aStarSearch(MazeCell start){
		fringe.add(start);
		boolean done = false;
		return done;
	}


	void expand(MazeCell curr){ //I think this needs to return an arraylist of mazecells, not void
		MazeCell temp;
		
		temp = curr.getNorthNeighbor();
		if(!temp.isVisited()){
			temp.parent = curr;
			fringe.add(temp);
		}
		
		temp = curr.getEastNeighbor();
		if(!temp.isVisited()){
			temp.parent = curr;
			fringe.add(temp);
		}		
		
		temp = curr.getSouthNeighbor();
		if(!temp.isVisited()){
			temp.parent = curr;
		fringe.add(temp);
		}
		
		temp = curr.getWestNeighbor();
		if(!temp.isVisited()){
			temp.parent = curr;
			fringe.add(temp);
		}
	}
	
	/**
	 * This function is responsible for "solving" the maze. Solving the maze
	 * represents finding a path from the start MazeCell to the finish MazeCell.
	 * We do this using search, and at each step, we call setVisited(true)
	 * and setUsed(true) so that the draw code can represent our partial
	 * solution. If no path can be found, solve will return false.
	 * 
	 * @param start
	 *            The cell from whence the search originates
	 * @return
	 */
	public boolean solve(MazeCell start) {
		
		boolean completed=false;
		 //Breadth first algo
		if(searchMode == BREADTH_FIRST_SEARCH){
			completed = breadthFirstSearch(start);
		}
		
		//Depth_first algo
		if(searchMode == DEPTH_FIRST_SEARCH){
		completed=depthFirstSearch(start);
			
		}
		
		
		//Iterative
		if(searchMode == ITERATIVE_DEEPENING_DEPTH_FIRST_SEARCH){
			completed = iDDFS(start);
		}
		
		//A-Star
		if(searchMode == A_STAR_SEARCH){
			completed = aStarSearch(start);
			
		}
	
		return completed;
	}

	private boolean GraphSearch(){
		if(fringe.isEmpty()) return false;
		MazeCell current = fringe.get(0);
		if(current.isFinish()){
			while(!current.isStart()){
				current.setUsed(true);
				current = current.parent;
			}
			
			return true;
		}
		
		if(current.isVisited()){
			fringe.remove(0);
			return false;
		}
		
		else{
			expand(current);
			current.setVisited(true);
			closedList.add(current);
			fringe.remove(0);
			return false;
		}
		
		
	}
	
	private void clearMaze() {
		for (int i = 0; i < maxX; ++i)
			for (int j = 0; j < maxY; ++j) {
				cells[i][j].setVisited(false);
			}
	}

	/**
	 * Inner class responsible for responding to clicks of the start button.
	 */
	public class StartListener implements ActionListener, Runnable {
		public void actionPerformed(ActionEvent arg0) {
			clearMaze();
			running = true;
			Thread runSearch = new Thread(this);
			runSearch.start();
		}

		public void run() {
			while (running) {
				try {
					Thread.sleep(50);
				} catch (Exception e) {
				}
				solve(cells[startXIdx][startYIdx]);
				running = false;
			}
		}
	}

	/**
	 * Returns the MazeCell that is the starting cell
	 * 
	 * @return The MazeCell that is the starting cell
	 */
	public MazeCell getStartCell() {
		return this.startCell;
	}

	/**
	 * Returns the MazeCell that is the finish cell
	 * 
	 * @return The MazeCell that is the finish cell
	 */
	public MazeCell getFinishCell() {
		return this.finishCell;
	}

}
